package cn.zyl.demo.common.gif;

import java.io.OutputStream;
import java.io.IOException;

/**
 * EncoderLZW 类说明: 通过J.M. G. Elliott改编自Jef的Java端口。
 * <p>
 *  算法：
 *   在前缀代码/下一个字符组合上使用开放式寻址双哈希（不链接）。我们对Knuth的算法D（第3卷，第6.4节）和G.的相对素数的
 *   辅助探针进行了变体。在这里，模块化除法运算的第一个探针被允许更快的异或操作。也可以使用
 *   自适应复位来进行块压缩，从而在压缩比减小时在表填满后清除代码表。此时将对可变长度输出代码
 *   进行大小调整，并为解压缩器生成特殊的CLEAR代码。后期添加：根据
 *   文件大小构造表，以显着提高小文件的速度。
 *   请将有关此实现的问题发送给！jaw。
 * </p>
 * <p>
 *  GifComPr.C       - GIF图像压缩程序<br>
 *  LemPel -基于'压缩'的Ziv压缩.  GIF修改者<br>
 *  David RowLey (mgardi@watdcsu.waterloo.edu)<br>
 *  一般定义<br>
 *  GIF图像压缩-修改的“压缩”<br>
 *  基于: compress.c - 文件压缩ala IEEE计算机, June 1984.<br>
 *  作者:
 *      Spencer W. Thomas      (decvax!harpo!utah-cs!utah-gr!thomas)<br>
 *      Jim McKie              (decvax!mcvax!jim)<br>
 *      Steve Davies           (decvax!vax135!petsd!peora!srd)<br>
 *      Ken Turkowski          (decvax!decwrl!turtlevax!ken)<br>
 *      James A. Woods         (decvax!ihnp4!ames!jaw)<br>
 *      Joe Orost              (decvax!vax135!petsd!joe)<br>
 * </p>
 * @author wsz K Weiner 12/00
 * @version v1.0
 * @date 2020-08-19 <a href="https://blog.csdn.net/joliny/article/details/3357179">源码</a>
 */
class EncoderLZW {
    private static final int EOF = -1;
    /** 80% 占用,用于动态表大小调整 */
    private static final int H_SIZE = 5003;
    /** 用户可设置的最大＃位/代码*/
    private static final int MAX_BITS = 12;
    /** 永远不要生成此代码*/
    private static final int MAX_MAX_CODE = 1 << MAX_BITS;
    private static final int[] MASKS = {0x0000, 0x0001, 0x0003, 0x0007, 0x000F, 0x001F, 0x003F, 0x007F, 0x00FF, 0x01FF, 0x03FF, 0x07FF, 0x0FFF, 0x1FFF, 0x3FFF, 0x7FFF, 0xFFFF };

    private final int width;
    private final int height;
    private final int initCodeSize;

    private final int[] hashTab = new int[H_SIZE];
    private final int[] codeTab = new int[H_SIZE];
    private final byte[] pixAry;
    /** 定义数据包累加器的存储 */
    private final byte[] acc = new byte[256];

    private int remaining;
    private int curPixel;
    /** 数量 位/代码*/
    private int nBits;
    /** 给定n_bits的最大代码*/
    private int maxCode;
    /**第一个未使用的条目*/
    private int freeEnt = 0;
    private int gInitBits;
    private int clearCode;
    private int eofCode;
    private int curAcc = 0;
    private int curBits = 0;
    /** 到目前为止，此“数据包”中的字符数*/
    private int byteCount;

    /** 块压缩参数-在所有代码用完并且压缩率更改后，重新开始。*/
    private boolean clearFlg = false;

    /**
     * <pre>
     *     output 输出给定的代码。
     *     Inputs: 代码:   一个n_bits位的整数  If == -1, then EOF.  假设 n_bits =< wordSize - 1.
     *     Outputs: 将代码输出到文件
     *     Assumptions: 字符长8位
     *     Algorithm: 保持BITS字符长的缓冲区（以便8个代码完全适合其中）。使用VAX insv指令依次插入每个代码。当缓冲区填满时，将其重新开始
     * </pre>
     * @param width 宽
     * @param height 高
     * @param pixels 像素
     * @param colorDepth 颜色深度
     */
    EncoderLZW(int width, int height, byte[] pixels, int colorDepth) {
        this.width = width;
        this.height = height;
        pixAry = pixels;
        initCodeSize = Math.max(2, colorDepth);
    }
    /** 在当前数据包的末尾添加一个字符，如果它是254个字符，则将数据包刷新到磁盘。*/
    private void charOut(byte c, OutputStream outs) throws IOException {
        acc[byteCount++] = c;
        if (byteCount >= 254) {
            flushChar(outs);
        }
    }
    /** 清除哈希表，清除表以进行块压缩*/
    private void clearBlock(OutputStream outs) throws IOException {
        clearHash(H_SIZE);
        freeEnt = clearCode + 2;
        clearFlg = true;
        output(clearCode, outs);
    }
    /** 重置码表 */
    private void clearHash(int size) {
        for (int i = 0; i < size; ++i) {
            hashTab[i] = -1;
        }
    }
    void compress(int initBits, OutputStream outs) throws IOException {
        int code,i,c,ent,disp,hSizeReg,hShift;
        //设置全局变量：g_init_bits-初始位数
        gInitBits = initBits;
        //设置必要的值
        clearFlg = false;
        nBits = gInitBits;
        maxCode = maxCode(nBits);

        clearCode = 1 << (initBits - 1);
        eofCode = clearCode + 1;
        freeEnt = clearCode + 2;
        //清除数据包
        byteCount = 0;

        ent = nextPixel();
        hShift = 0;
        for (code = H_SIZE; code < 65536; code *= 2) {
            ++hShift;
        }
        //设置哈希码范围限制
        hShift = 8 - hShift;
        hSizeReg = H_SIZE;
        //清除哈希表
        clearHash(hSizeReg);
        output(clearCode, outs);

        outerLoop : while ((c = nextPixel()) != EOF) {
            code = (c << MAX_BITS) + ent;
            // 异或哈希
            i = (c << hShift) ^ ent;
            if (hashTab[i] == code) {
                ent = codeTab[i];
                continue;
                // 非空插槽
            } else if (hashTab[i] >= 0) {
                // 二次哈希
                disp = hSizeReg - i;
                if (i == 0) {
                    disp = 1;
                }
                do {
                    if ((i -= disp) < 0) {
                        i += hSizeReg;
                    }
                    if (hashTab[i] == code) {
                        ent = codeTab[i];
                        continue outerLoop;
                    }
                } while (hashTab[i] >= 0);
            }
            output(ent, outs);
            ent = c;
            if (freeEnt < MAX_MAX_CODE) {
                // code -> hashtable
                codeTab[i] = freeEnt++;
                hashTab[i] = code;
            } else {
                clearBlock(outs);
            }
        }
        //推出最终代码。
        output(ent, outs);
        output(eofCode, outs);
    }
    public void encode(OutputStream os) throws IOException {
        //写入“初始代码大小”字节
        os.write(initCodeSize);
        //重置导航变量
        remaining = width * height;
        curPixel = 0;
        //压缩和写入像素数据
        compress(initCodeSize + 1, os);
        // 写块终止符
        os.write(0);
    }
    /** 将数据包刷新到磁盘，然后重置累加器 */
    public void flushChar(OutputStream outs) throws IOException {
        if (byteCount > 0) {
            outs.write(byteCount);
            outs.write(acc, 0, byteCount);
            byteCount = 0;
        }
    }
    private int maxCode(int bit) {
        return (1 << bit) - 1;
    }
    /** 返回图像的下一个像素*/
    private int nextPixel() {
        if (remaining == 0) {
            return EOF;
        }
        --remaining;
        byte pix = pixAry[curPixel++];
        return pix & 0xff;
    }
    void output(int code, OutputStream outs) throws IOException {
        curAcc &= MASKS[curBits];
        if (curBits > 0) {
            curAcc |= (code << curBits);
        }else {
            curAcc = code;
        }
        curBits += nBits;
        while (curBits >= 8) {
            charOut((byte) (curAcc & 0xff), outs);
            curAcc >>= 8;
            curBits -= 8;
        }
        // 如果下一个条目对于代码大小而言太大，那么请尽可能增加它。
        if (freeEnt > maxCode || clearFlg) {
            if (clearFlg) {
                maxCode = maxCode(nBits = gInitBits);
                clearFlg = false;
            } else {
                ++nBits;
                if (nBits == MAX_BITS) {
                    maxCode = MAX_MAX_CODE;
                } else {
                    maxCode = maxCode(nBits);
                }
            }
        }
        if (code == eofCode) {
            // 在EOF处，写入其余缓冲区。
            while (curBits > 0) {
                charOut((byte) (curAcc & 0xff), outs);
                curAcc >>= 8;
                curBits -= 8;
            }
            flushChar(outs);
        }
    }
}
